package leetcode.code1707;

import leetcode.IDebug;
import leetcode.helper.HelpDebug;

public class Solution implements IDebug {

	Node root;

	int High = 30;// 最高位30 最低位1

	public int[] maximizeXor(int[] nums, int[][] queries) {
		root = new Node(High);
		for (int num : nums) {
			root.add(num);
		}
		int len = queries.length;
		int[] ans = new int[len];
		for (int i = 0; i < len; i++) {
			int[] query = queries[i];
			int xi = query[0];
			int mi = query[1];
			ans[i] = root.find(xi, mi);
		}
		return ans;
	}

	class Node {
		Node zero;
		Node one;

		int min;
//		int max; // min够用了，max没用上
		// 对应pos获取相应位数是不是0，
		// 如pos=30，AND=100000000000000000000000000000
		int AND;
		// 1e9 是111011100110101100101000000000 最低1位最高30位，左侧是高位
		int pos;// 第几位数

		public Node(int pos) {
			this.min = Integer.MAX_VALUE;
//			this.max = Integer.MIN_VALUE;
			this.pos = pos;
			this.AND = 1 << (pos - 1);
		}

		public int find(int xi, int max) {
			if (max < min) {// 如果 nums 中的所有元素都大于 mi，最终答案就是 -1
				return -1;
			}
			Node node = this;
			int ans = 0;
			for (int i = High; i >= 1; i--) {// 从高位向低位找答案，越早选1越好
				int pxi = node.AND & xi;// pxi是1，尽量在num上选0，pxi是0尽量选1
				if (pxi == 0) {// xi这一位是0
					// nums中这一位能不能选1
					if (node.one != null && max >= node.one.min) {// 有1 并且 选了1后有小于等于max的数
						ans |= node.AND;
						node = node.one;
					} else {
						node = node.zero;
					}
				} else {// xi这一位是1
					// nums中这一位能不能选0
					if (node.zero != null && max >= node.zero.min) {
						ans |= node.AND;
						node = node.zero;
					} else {
						node = node.one;
					}
				}
			}
			return ans;
		}

		public void add(int num) {
//			if (num > max) {
//				max = num;
//			}
			if (num < min) {
				min = num;
			}
			if (pos == 0) {// 必须在min和max后边，决定了最后一位数字是否可选，为了node.zero.min判断用
				return;
			}
			if ((num & AND) == 0) {// AND这一位在num上是0
				if (this.zero == null) {
					this.zero = new Node(this.pos - 1);
				}
				this.zero.add(num);
			} else {// AND这一位在num上是1
				if (this.one == null) {
					this.one = new Node(this.pos - 1);
				}
				this.one.add(num);
			}
		}
	}

	@Override
	public void debug1() {
		int[] e = HelpDebug.str2array3("[3,3,7]");
		HelpDebug.compare(e, this.maximizeXor(HelpDebug.str2array3("[0,1,2,3,4]"), HelpDebug.str2array1("[[3,1],[1,3],[5,6]]")));
	}

	@Override
	public void debug2() {
		int[] e = HelpDebug.str2array3("[-1,-1,3,]");
		HelpDebug.compare(e, this.maximizeXor(HelpDebug.str2array3("[9,21,6,15,14]"), HelpDebug.str2array1("[[3,1],[1,3],[5,6]]")));
	}

	@Override
	public void debug3() {
		int[] e = HelpDebug.str2array3("[15,-1,5,125,5]");
		HelpDebug.compare(e, this.maximizeXor(HelpDebug.str2array3("[5,2,4,6,6,3,123]"),
				HelpDebug.str2array1("[[12,4],[8,1],[6,3],[6,256],[1,4]]")));
	}

	@Override
	public void debug4() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
//		so.debug4();
		int e = (int) 1e9;
		System.out.println(e);
		System.out.println(Integer.toBinaryString(e));
		System.out.println(Integer.toBinaryString(1 << 29));
//		System.out.println(so.highPos(8));
	}

}
